package leetcode.editor.cn.q1_300.q50;

class UniquePaths {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int uniquePaths(int m, int n) {
            int[][] arr = new int[m][n];

            for (int i = 0; i < m; i++) {
                arr[i][0] = 1;
            }

            for (int i = 0; i < n; i++) {
                arr[0][i] = 1;
            }

            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
                }
            }

            return arr[m - 1][n - 1];
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new UniquePaths().new Solution();
        System.out.println(solution.uniquePaths(1, 1));
        System.out.println(solution.uniquePaths(3, 7));
        System.out.println(solution.uniquePaths(3, 2));
    }
}